﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Threading.Tasks;

namespace doveData
{
    class StationGraph<T>//图
    {
        private List<Vertex<T>> items;//图的顶点集合
        private int capacity;


        public StationGraph() : this(10) { }//构造方法

        /// <summary>
        /// 
        /// </summary>
        /// <param name="cap">所有站点的数量</param>
        public StationGraph(int cap)//指定容量的构造方法
        {
            capacity = cap;
            items = new List<Vertex<T>>(cap);
        }


        public int Count
        {
            get { return items.Count; }
        }

        public int Capacity
        {
            get { return capacity; }
        }

        /// <summary>
        /// 通过索引获取其中的值
        /// </summary>
        /// <param name="index">item所在的位置</param>
        /// <returns></returns>
        public T GetItem(int index)//索引器
        {
            if (index >= 0 && index <= items.Count - 1)
            {
                return items[index].data;
            }
            else
            {
                throw new Exception("索引超出范围！");
            }
        }

        

        /// <summary>
        /// 在图顶点表最后添加一个顶点
        /// </summary>
        /// <param name="item"></param>
        public void AddVertex(T item)
        {
            if (Count == capacity) //已经满了
            {
                capacity *= 2;
                List<Vertex<T>> newList=new List<Vertex<T>>(capacity);
                newList.AddRange(items);
                items = newList;
            }
            //不允许插入重复值
            if (Contains(item))
            {
                //throw new ArgumentException("插入了重复顶点！");
                Console.WriteLine("插入了重复顶点:{0}！",item);
                return;
            }
            items.Add(new Vertex<T>(item));

        }


        public void InsertVertex(T item)//向某处插入
        {
            //TODO
        }

        /// <summary>
        /// 添加无向边
        /// </summary>
        /// <param name="from">边的一个端点</param>
        /// <param name="to">另一个端点</param>
        public void AddEdge(T from, T to)
        {
            Vertex<T> fromVer = Find(from);
            if (fromVer == null)
            {
                //throw new ArgumentException("头顶点不存在!");
                Console.WriteLine("头顶点不存在!");
                return;
            }
            Vertex<T> toVer = Find(to);
            if (toVer == null)
            {
               // throw new ArgumentException("尾顶点不存在！");
                Console.WriteLine("尾顶点不存在！");
                return;
            }
            //无向边的两个顶点都需记录边信息
            AddDirectedEdge(fromVer, toVer);
            AddDirectedEdge(toVer, fromVer);
        }



        /// <summary>
        /// 利用引用查找图中是否包含某项
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        public bool Contains(T item)//查找图中是否包含某项
        {
            foreach (Vertex<T> v in items)
            {
                if (v.data.Equals(item))
                {
                    return true;
                }
            }
            return false;
        }



        /// <summary>
        /// 利用引用查找指定项并返回
        /// </summary>
        /// <param name="item"></param>
        /// <returns></returns>
        private Vertex<T> Find(T item)
        {
            foreach (Vertex<T> v in items)
            {
                if (v.data.Equals(item))
                {
                    return v;
                }
            }
            return null;
        }




        /// <summary>
        /// 添加有向边
        /// </summary>
        /// <param name="fromVer"></param>
        /// <param name="toVer"></param>
        private void AddDirectedEdge(Vertex<T> fromVer, Vertex<T> toVer)
        {
            if (fromVer.firstEdge == null)//无邻接点时
            {
                fromVer.firstEdge = new Node(toVer);
            }
            else
            {
                Node tmp,//用于表示链表末尾结点
                    node = fromVer.firstEdge;//下一结点
                do
                {
                    //检查是否添加了重复边
                    if (node.headvex.data.Equals(toVer.data))
                    {
                       // throw new ArgumentException("添加了重复的边！");
                        Console.WriteLine("添加了重复的边:{0}->{1}！",fromVer.data,toVer.data );
                        return;
                    }
                    tmp = node;
                    node = node.next;
                } while (node != null);
                tmp.next = new Node(toVer);//添加到链表末尾
            }
        }

        public override string ToString() //仅用于测试
        {   //打印每个节点和它的邻接点
            string s = string.Empty;
            foreach (Vertex<T> v in items)
            {
                s += v.data.ToString() + ":";
                if (v.firstEdge != null)
                {
                    Node tmp = v.firstEdge;
                    while (tmp != null)
                    {
                        s += "、";
                        s += tmp.headvex.data.ToString();
                        tmp = tmp.next;
                    }
                }
                s += "\r\n";
            }
            return s;
        }





        #region 嵌套类 结点Node 表头Vertex
        //链表中的表结点
        public class Node
        {
            public Vertex<T> headvex;//邻接点域
            public Node next;//下一个邻接点域

            public Node(Vertex<T> value)
            {
                headvex = value;
            }
        }



        //表示存放于数组中的表头结点
        public class Vertex<TValue>
        {
            public TValue data;//数据
            public Node firstEdge;//邻接点链表头指针
            public Boolean visited;//访问标记

            public Vertex(TValue value)//构造方法
            {
                data = value;
            }
        }
        #endregion


    }

}
